import java.time.temporal.ValueRange;

// 二叉树按层序列化和反序列化(中序实现)
public class LevelOrderSerializeAndDeserialize {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    public class Codec {

        TreeNode[] queue = new TreeNode[10001];
        int l,r;

        //序列化 中序遍历
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            l=0;r=0;
            if(root != null) {
                queue[r++] = root;
                sb.append(root.val + ",");
            }else{
                return sb.toString();
            }
            while (l < r) {
                int size = r - l;
                for(int i = 0; i < size; ++i) {
                    TreeNode node = queue[l++];
                    if(node.left != null) {
                        queue[r++] = node.left;
                        sb.append(node.left.val + ",");
                    }else {
                        sb.append("#,");
                    }

                    if(node.right != null) {
                        queue[r++] = node.right;
                        sb.append(node.right.val + ",");
                    }else {
                        sb.append("#,");
                    }
                }

            }
            return sb.toString();
        }

        //反序列化

        public TreeNode deserialize(String data) {
            if(data.equals("")) {
                return null;
            }
            String[] arr = data.split(","); //分割数组
            l = 0;  r = 0;
            queue[r] = new TreeNode(Integer.valueOf(arr[r++]) );
            int cnt = 1;  //记录消耗元素的下标
            while (l < r) {
                TreeNode cur = queue[l++];
                cur.left = arr[cnt].equals("#") ? null : new TreeNode(Integer.valueOf(arr[cnt]) );
                cnt++;
                cur.right = arr[cnt].equals("#") ? null : new TreeNode(Integer.valueOf(arr[cnt]) );
                cnt++;
                if(cur.left != null) {
                    queue[r++] = cur.left;
                }
                if(cur.right != null) {
                    queue[r++] = cur.right;
                }
            }

            return queue[0];
        }
    }
}
